# 
# Created by francklinson on 2021/10/8 AT 10:26.
#
from collections import defaultdict
from typing import List


class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        retList = []
        if len(s) <= 10:
            return retList
        subStrCounter = defaultdict(int)
        for i in range(len(s) - 10 + 1):
            curStr = s[i:i + 10]
            subStrCounter[curStr] += 1
            if subStrCounter[curStr] == 2:
                retList.append(curStr)
        return retList


L = 10
bin = {'A': 0, 'C': 1, 'G': 2, 'T': 3}


class Solution2:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        # 每个长度为10的字符串 用一个整数代替
        n = len(s)
        if n <= L:
            return []
        ans = []
        x = 0
        for ch in s[:L - 1]:
            x = (x << 2) | bin[ch]
        cnt = defaultdict(int)
        for i in range(n - L + 1):
            x = ((x << 2) | bin[s[i + L - 1]]) & ((1 << (L * 2)) - 1)
            cnt[x] += 1
            if cnt[x] == 2:
                ans.append(s[i: i + L])
        return ans


if __name__ == '__main__':
    sol = Solution2()
    print(sol.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"))
    print(sol.findRepeatedDnaSequences("AAAAAAAAAAAAA"))
